//package 二叉树;
//
//class BinaryNode<T> {
//    public T data;
//    public BinaryNode<T> parent, child, sibling;
//
//    // 构造函数
//    public BinaryNode(T data, BinaryNode<T> parent, BinaryNode<T> child, BinaryNode<T> sibling) {
//        this.data = data;
//        this.parent = parent;
//        this.child = child;
//        this.sibling = sibling;
//    }
//
//}
//
//public class Tree<T> {
//    public BinaryNode<T> root;
//    public int i = 0;
//
//    public Tree() {
//        this.root = null;
//    }
//
//    public Tree(T x) {
//        this.root = new BinaryNode<>(x, null, null, null);
//    }
//
//    public BinaryNode<T> insert(T x, BinaryNode<T> parent) {
//        BinaryNode<T> child = new BinaryNode<>(x, parent, null, null);
//        if (parent.child != null) {
//            BinaryNode<T> temp = parent.child;
//            while (temp.sibling != null) {
//                temp = temp.sibling;
//            }
//            temp.sibling = child;
//        } else {
//            parent.child = child;
//        }
//        return child;
//    }
//
//
//    public static void main(String[] args) {
//        Tree<Integer> tree1 = new Tree<>(1);
//        BinaryNode<Integer> child_2 = tree1.insert(2, tree1.root);
//        BinaryNode<Integer> child_3 = tree1.insert(3, tree1.root);
//        tree1.insert(6, child_3);
//        BinaryNode<Integer> child_4 = tree1.insert(4, child_2);
//        tree1.insert(5, child_2);
//        tree1.insert(7, child_4);
//        BinaryNode<Integer> child_8 = tree1.insert(8, child_4);
//        tree1.insert(9, child_8);
//        tree1.printTree(tree1.root, "");
//        System.out.println("------------------");
//        Tree<Integer> tree2 = new Tree<>(4);
//        tree2.insert(7, tree2.root);
//        BinaryNode<Integer> child_8_2 = tree2.insert(8, tree2.root);
//        tree2.insert(9, child_8_2);
//        tree2.printTree(tree2.root, "");
//        tree1.removeAll(tree2);
//
//
//    }
//
//    public void removeAll(Tree tree) {
//        BinaryNode[] treeNodes = new BinaryNode[100];
//        preorder(this.root, treeNodes);
//        for (BinaryNode notes : treeNodes) {
//            if (notes != null) {
//                if (notes.data.equals(tree.root.data) && Equals(notes, tree.root)) {
//                    //通过父节点遍历到本节点上一个节点
//                    BinaryNode t = notes.parent;
//                    if (t == null) {
//                        this.root = null;
//                    } else if (t.child == notes) {
//                        t.child = t.child.sibling;
//                    } else {
//                        t = t.child;
//                        while (t.sibling != null) {
//                            if (t.sibling == notes) {
//                                System.out.println(t.sibling.data);
//                                t.sibling = null;
//                            }
//                            t = t.sibling;
//                        }
//                    }
//                }
//            }
//        }
//        System.out.println("删除重复后");
//        this.printTree(this.root, "");
//    }
//
//    public void printTree(BinaryNode<T> node, String indent) {
//        if (node == null) return;
//        System.out.println(indent + node.data);
//        printTree(node.child, indent + "  ");
//        printTree(node.sibling, indent);
//    }
//
//
//    public void preorder(BinaryNode<T> p, BinaryNode[] childs) {
//        if (p != null) {
//            childs[i++] = p;
//            for (BinaryNode<T> q = p.child; q != null; q = q.sibling)
//                preorder(q, childs);
//        }
//    }
//
//    public static <T> boolean Equals(BinaryNode<T> x1, BinaryNode<T> x2) {
//        //得到所有孩子
//        BinaryNode<T>[] childs1;
//        childs1 = getTreeChilds(x1);
//        BinaryNode<T>[] childs2;
//        childs2 = getTreeChilds(x2);
//
//        //判断孩子是否数量相同
//        int i = 0, j = 0, cnt1 = 0, cnt2 = 0;
//        while (childs1[i++] != null) {
//            cnt1 += 1;
//        }
//        while (childs1[j++] != null) {
//            cnt2 += 1;
//        }
//        if (cnt1 != cnt2)
//            return false;
//        for (BinaryNode<T> ch1 : childs1) {
//            if (ch1 != null) {
//                T data = ch1.data;
//                boolean flag = false;
//                for (BinaryNode<T> ch2 : childs2) {
//                    if (ch2 != null) {
//                        if (ch2.data.equals(data)) {
//                            flag = true;
//                        }
//                    }
//                }
//                if (!flag)
//                    return false;
//            }
//        }
//        for (BinaryNode<T> tTreeNode : childs1) {
//            if (tTreeNode != null) {
//                T data = tTreeNode.data;
//                for (BinaryNode<T> treeNode : childs2) {
//                    if (treeNode != null) {
//                        if (treeNode.data.equals(data)) {
//                            if (!Equals(tTreeNode, treeNode)) {
//                                return false;
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        return true;
//    }
//
//    public static BinaryNode[] getTreeChilds(BinaryNode p) {
//        BinaryNode[] Treechilds = new BinaryNode[100];
//        BinaryNode t = p.child;
//        int i = 0;
//        if (t != null) {
//            Treechilds[i++] = t;
//            while (t.sibling != null) {
//                Treechilds[i++] = t.sibling;
//                t = t.sibling;
//            }
//        }
//        return Treechilds;
//    }
//}
//
